class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int INF = 0x3f3f3f3f;
        int[] dp = new int[amount + 1];
        for(int j = 1; j <= amount; j++) dp[j] = INF;
        for(int i = 1; i <= n; i++){
            for(int j = coins[i - 1]; j <= amount; j++){
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[amount] >= INF ? -1 : dp[amount];
    }
}